package com.squirrel.michale.sort3;

/**
 * @author guanhao 观浩
 * @version 1.0.0.0
 * @createTime 2023/2/3 4:38 PM
 * @company Michale Squirrel
 * @link
 * @description
 */
public class LeetCode2545_2 {


    public int[][] sortTheStudents(int[][] score, int k) {
        int m = score.length;
        int[] indices = new int[m];
        for (int i = 0; i < m; i++) {
            indices[i] = i;
        }
        quickSort(score, indices, 0, m - 1, k);
        int[][] result = new int[m][];
        for (int i = 0; i < m; i++) {
            result[i] = score[indices[i]];
        }
        return result;
    }

    private void quickSort(int[][] score, int[] indices, int low, int high, int k) {
        if (low < high) {
            int pivotIndex = partition(score, indices, low, high, k);
            quickSort(score, indices, low, pivotIndex - 1, k);
            quickSort(score, indices, pivotIndex + 1, high, k);
        }
    }

    private int partition(int[][] score, int[] indices, int low, int high, int k) {
        int pivot = score[indices[high]][k];
        int i = low - 1;
        for (int j = low; j < high; j++) {
            if (score[indices[j]][k] >= pivot) {
                i++;
                swap(indices, i, j);
            }
        }
        swap(indices, i + 1, high);
        return i + 1;
    }

    private void swap(int[] indices, int i, int j) {
        int temp = indices[i];
        indices[i] = indices[j];
        indices[j] = temp;
    }
}
